package 回溯;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 组合77.java
 * @createTime 2022年10月31日 20:28:00
 */
public class 组合77 {
	List<List<Integer>> result = new ArrayList<>();

	public List<List<Integer>> combine(int n, int k) {
		//个数大于范围
		if (k > n) {
			return result;
		}
		int[] nums = new int[n];
		for (int i = 1; i <= n; i++) {
			nums[i - 1] = i;
		}
		backTrace(nums, k, 0, new boolean[nums.length]);
		return result;
	}

	LinkedList<Integer> list = new LinkedList<>();

	public void backTrace(int[] nums, int k, int curIndex, boolean[] used) {
		//结束条件
		if (list.size() == k) {
			result.add(new ArrayList<>(list));
			return;
		}

		for (int i = curIndex; i < nums.length; i++) {
			//条件判断，做选择
			if (used[i]) {
				continue;
			}

			list.add(nums[i]);
			used[i] = true;
			//继续回溯
			backTrace(nums, k, i + 1, used);
			//撤销选择
			list.removeLast();
			used[i] = false;
		}
	}
}
